10224. Articulation points – Timestamps
An undirected
graph is given. Run a depth first search from the given vertex v. Print the timestamps d[v] and up[v] for each vertex v in
the increasing order of vertices.
Input. The first line contains the number of
vertices n (n ≤ 100) and edges m of an undirected graph. Each of
the next m lines contains two
vertices a and b – an undirected edge of the graph. The last line contains
vertex v.
Output. Run dfs(v).
Print the timestamps d[v] and up[v] for each vertex v (v = 1, 2, ..., n). The timestamps for each vertex must
be printed on a separate line.
Hint. Use the adjacency matrix to get accepted.
Sample
input 1 |
Sample
output 1 |
6 8 6 5 6 3 5 3 4 5 3 4 3 2 1 2 1 3 1 |
1 1 2 1 3 1 4 3 5 3 6 3 |
|
|
Sample
input 2 |
Sample
output 2 |
7 9 1 2 2 3 1 3 3 4 2 5 4 5 4 6 4 7 6 7 1 |
1 1 2 1 3 1 4 2 5 2 6 4 7 4 |
graphs – articulation
points
The labels d[v] / up[v]
are used to find articulation points. Perform a depth first search and set up
the indicated labels.
Example
Place the labels in the graphs given in the first and second test cases.
Algorithm realization
Declare the adjacency matrix g and the arrays used, d and up.
#define MAX 101
int g[MAX][MAX];
int used[MAX], d[MAX], up[MAX];
Function dfs runs the depth-first search and
sets up the labels d[v] and up[v].
void dfs(int v, int p = -1)
{
used[v] = 1;
d[v] = up[v] = tm++;
for (int i = 1; i <= n; i++)
{
if (g[v][i] == 0) continue;
if (i == p) continue;
if (used[i])
up[v] = min(up[v], d[i]);
else
{
dfs(i, v);
up[v] = min(up[v], up[i]);
}
}
}
The
main part of the program. Read the input data. Fill in the adjacency matrix of
the graph g.
scanf("%d %d", &n,
&m);
for (i = 0; i < m; i++)
{
scanf("%d %d", &a,
&b);
g[a][b]
= g[b][a] = 1;
}
Read
the vertex v and start the depth-first
search from it.
scanf("%d", &v);
tm = 1;
dfs(v);
For each vertex, print the labels d[v] and up[v].
for (i = 1; i <= n; i++)
printf("%d %d\n", d[i],
up[i]);